package utils;

import java.util.Arrays;
import java.util.Random;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/30 9:28
 * @description: 工具类
 */
public class Utils {
    public static void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
    public static void shuffle(int[] nums) {
        Random r = new Random();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int j = i + r.nextInt(n - i);
            swap(nums, i, j);
        }
    }
    /**
     * 在指定范围内查找第一个大于等于目标值的元素位置
     * @param array 已排序的数组
     * @param fromIndex 起始索引（包含）
     * @param toIndex 结束索引（不包含）
     * @param target 目标值
     * @return 第一个大于等于目标值的元素索引，若未找到则返回toIndex
     */
    public static int lowerBound(int[] array, int fromIndex, int toIndex, int target) {
        // 参数校验
        checkBounds(array.length, fromIndex, toIndex);

        int left = fromIndex;
        int right = toIndex;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 在指定范围内查找第一个大于目标值的元素位置
     * @param array 已排序的数组
     * @param fromIndex 起始索引（包含）
     * @param toIndex 结束索引（不包含）
     * @param target 目标值
     * @return 第一个大于目标值的元素索引，若未找到则返回toIndex
     */
    public static int upperBound(int[] array, int fromIndex, int toIndex, int target) {
        // 参数校验
        checkBounds(array.length, fromIndex, toIndex);

        int left = fromIndex;
        int right = toIndex;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (array[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 简化版本，默认查找整个数组
     */
    public static int lowerBound(int[] array, int target) {
        return lowerBound(array, 0, array.length, target);
    }

    /**
     * 简化版本，默认查找整个数组
     */
    public static int upperBound(int[] array, int target) {
        return upperBound(array, 0, array.length, target);
    }

    /**
     * 参数边界校验
     */
    private static void checkBounds(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException("fromIndex = " + fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException("toIndex = " + toIndex);
        }
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 3, 5, 7, 9, 9, 11};
        System.out.println("数组: " + Arrays.toString(array));

        // 测试整个数组范围
        int target = 3;
        System.out.println("\n目标值: " + target + "，查找范围: 0-" + array.length);
        System.out.println("lowerBound位置: " + lowerBound(array, 0, array.length, target)); // 输出1
        System.out.println("upperBound位置: " + upperBound(array, 0, array.length, target)); // 输出3

        // 测试指定范围
        System.out.println("\n目标值: " + target + "，查找范围: 2-6");
        System.out.println("lowerBound位置: " + lowerBound(array, 2, 6, target)); // 输出2
        System.out.println("upperBound位置: " + upperBound(array, 2, 6, target)); // 输出3

        // 测试目标值为9，指定范围
        target = 9;
        System.out.println("\n目标值: " + target + "，查找范围: 0-8");
        System.out.println("lowerBound位置: " + lowerBound(array, 0, 8, target)); // 输出5
        System.out.println("upperBound位置: " + upperBound(array, 0, 8, target)); // 输出7
    }
}
